import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 
 * 广度优先搜索（Breadth-First Search，简称 BFS）是一种图的遍历算法。
 * 
 * 广度搜索，顾名思义，就是更大范围内搜索，先访问完当前顶点的所有邻接点，然后再访问下一层的所有节点，该算法适用于解决最短、最小路径等问题，
 * 但是构建广度优先算法需要维护自己的队列。
广度搜索是同时搜索所有路径，相当于一层一层地搜索，就好比波浪的扩展一样。此搜索方法跟树的层次遍历类似，因此宽度搜索一般都用队列存储结构。

 * 
 * 广度优先搜索（Breadth-First Search，BFS）是一种图搜索算法，用于遍历或搜索图中的节点。它从一个起始节点开始，首先访问其所有相邻节点，
 * 然后依次访问这些相邻节点的相邻节点，依此类推，直到访问完所有节点或找到目标节点。以下是使用Java实现BFS算法的示例：
 */
public class 广度搜索demo {
    
    public static void main(String[] args) {

        BreadthGrash breadthGrash = new BreadthGrash(6);
        //构建 树 图
        breadthGrash.addLine(0, 1);
        breadthGrash.addLine(0, 2);
        breadthGrash.addLine(1, 3);
        breadthGrash.addLine(1, 4);
        breadthGrash.addLine(2, 4);
        breadthGrash.addLine(3, 4);
        breadthGrash.addLine(3, 5);
        breadthGrash.addLine(4, 5);

        System.out.println("开始执行广度优先搜索");

        breadthGrash.bfs(2);
        
    }

    private static class BreadthGrash{

        public int dataCount;
        //模拟图
        List<List<Integer>> dataMap;

        public BreadthGrash(int dataCount){
            this.dataCount = dataCount;
            dataMap = new ArrayList<>(dataCount);

            for(int i=0; i<dataCount; i++){
                dataMap.add(new ArrayList<>());
            }

        }

        public void addLine(int start, int end){
            dataMap.get(start).add(end);
        }

        public void bfs(int handle){

            if(handle<0 || handle>=dataCount){

                System.out.println("查找节点输入越界");

                return;
            }

            boolean[] isHandled = new boolean[dataCount];
            //处理队列
            Queue<Integer> queue = new LinkedList<>();

            isHandled[handle] = true;

            queue.add(handle);

            System.out.println(handle+"已处理");


            while (!queue.isEmpty()) {

                int handleV = queue.poll();

                List<Integer> subDataList = dataMap.get(handleV);
                if(null ==subDataList || subDataList.isEmpty()){

                    System.out.println("没有子节点，搜索结束");
    
                    return;
                }

                for(int subV : subDataList){

                    if(!isHandled[subV]){
                        isHandled[subV] = true;
                        System.out.println(subV+"已始处理");
                        queue.add(subV);
                    }

                }

            }

        }

    }
}
